/**
 * @author TrinhNX
 */
public class Euler014 {
	public static void main(String[] args) {
		//		int n = 3;
		final int MAX = 1000000;
		// long value because the 3* will raise the number very big.
		long start = System.currentTimeMillis();
		long sequenceLength = 0;
		long startingNumber = 0;
		long sequence = 0;

		long[] cache = new long[MAX + 1];
		//Initialise cache
		for (int i = 0; i < cache.length; i++) {
			cache[i] = -1;
		}
		cache[1] = 1;

		for (int i = 2; i <= MAX; i++) {
			sequence = i;
			long k = 0;
			while (sequence != 1 && sequence >= i) {
				k++;
				if ((sequence & 1) == 0) {
					sequence = sequence / 2;
				} else {
					sequence = sequence * 3 + 1;
				}
			}
			//Store result in cache
			System.out.println(i + "\t" + k + "\t" + sequence);
			cache[i] = k + cache[(int)sequence];

			//Check if sequence is the best solution
			if (cache[i] > sequenceLength) {
				sequenceLength = cache[i];
				startingNumber = i;
			}
		}
		System.out.println("Value: " + startingNumber + " chain: " + sequenceLength);
		System.out.println("Time: \t" + (System.currentTimeMillis() - start));
	}

	private int generateCollatzProblem(int n) {
		int i = 0;
		int temp = n;
		while (temp != 1) {
			if ((temp % 2) == 0) {
				temp = temp / 2;
			} else {
				temp = 3 * temp + 1;
			}
			i = i + 1;
		}
		return i;
	}

	private void solveCollatzProblem(int n, int count, final int MAX) {
		if (n < 4) {
			System.out.println("END:" + n + "\tCount: " + count);
			return;
		}
		if (n > MAX) {
			System.out.println("Count is: " + count + "\tN: " + n);
			return;
		}
		int n1 = n / 2;
		if ((n1 * 2 == n) && ((n1 % 2) == 0)) {
			int n2 = (n - 1) / 3;
			if (((n2 * 3 + 1) == n) && ((n2 % 3) == 1)) {
				solveCollatzProblem(n2, count + 1, MAX);
				solveCollatzProblem(n1, count + 1, MAX);
			} else {
				solveCollatzProblem(n1, count + 1, MAX);
			}
		} else {

		}
	}
}